/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution134 {

    public static void main(String args[]) {
        Solution134 s = new Solution134();
        System.out.println(s.canCompleteCircuit(new int[]{1, 2, 3, 3}, new int[]{2, 1, 5, 1}));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        if (n == 1) {
            return cost[0] - gas[0] > 0 ? -1 : 0;
        }

        int left[] = new int[n];
        int st = -1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            left[i] = gas[i] - cost[i];
            sum += left[i];
            if (left[i] >= 0 && st == -1) {
                st = i;
            }
        }
        if (sum < 0) {
            return -1;
        }

        int ed = st;
        int total = 0;
        total += left[st];
        st = (st + 1) % n;
        while (st != ed) {
            total += left[st];
            st = (st + 1) % n;
            if (total < 0) {
                ed = st;
                total = 0;
            }
        }
        return total >= 0 ? ed : -1;
    }

}
